import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 面试题 08.07. 无重复字符串的排列组合
 * https://leetcode-cn.com/problems/permutation-i-lcci/
 */
public class Solutions_mianshi_08_07 {
    public static void main(String[] args) {
        String s = "qwe";  // output: {"qwe", "qew", "wqe", "weq", "eqw", "ewq"}
        String[] result = permutation(s);
        System.out.println(Arrays.toString(result));
    }

    private static List<String> list = null;
    public static String[] permutation(String S) {
        if (S == null || S.length() < 1) {
            return new String[0];
        }
        char[] arr = S.toCharArray();
        list = new ArrayList<>();
        char[] res = new char[arr.length];
        backtrack(res, 0, arr);
        return list.toArray(new String[list.size()]);
    }

    public static void backtrack(char[] res, int index, char[] arr) {
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (Character.isLetter(c)) {
                // 添加结果
                res[index] = c;
                // 标记状态
                arr[i] = '#';
                if (index == arr.length - 1) {
                    // 结束条件：完成了一次排列组合
                    list.add(new String(res));
                } else {
                    // 递归
                    backtrack(res, index + 1, arr);
                }
                // 还原状态
                arr[i] = c;
            }
        }
    }
}
